import random
import networkx as nx
import matplotlib.pyplot as plt

#将集合关系图直观地显示出来
def drawgraph(R):
    G=nx.DiGraph()
    G.add_edges_from(R)
    nx.draw(G,node_size= 200,node_color='r', with_labels= True, font_color='w')
    plt.show()
    return

#构建函数f
def createfunction(X,Y):
    m=len(X)
    n=len(Y)
    f=set({})
    for k in range(m):
        if k%n==0:
            Y=random.sample(Y,n)
        f=f|{(X[k],Y[k%n])}
    return f

#获取定义域
def getdomain(f):
    X=set({})
    for (x,y) in f:
        X=X|{x} 
    return X

#获取值域
def getrange(f):
    Y=set({})
    for (x,y) in f:
        Y=Y|{y}
    return Y

#构建恒等函数
def Ixfunc(X):
    Ix=set({})
    for x in X:
        Ix.add((x,x))
    return Ix

#构建定义域为XxX，值域为Y的函数f
def createfunction1(m, n):
    X1 = range(m)
    X2= range(m)
    Y = range(n)
    f= set({})
    k=0
    for i in range(m):
        for j in range(m):
            if k % n == 0:
                Y= random.sample(Y,n)
            f=f| {(X1[i], X2[j], Y[k%n])}
            k=k+1
    return f

#构建双射函数
def bijectionfunc(X,Y):
    n=len(X)
    Y=random.sample(Y,n)
    f=set({})
    for k in range(n):
        f=f|{(X[k],Y[k])}
    return f

#判断双射函数
def isbijection(X, Y,f):
    tv=(getdomain(f)==set(X))&(getrange(f)==set(Y))
    return tv

#构建单射函数
def injunctionfunc(X,Y):
    m=len(X)
    Y=random.sample(Y,m)
    f=set({})
    for k in range(m):
        f=f|{(X[k],Y[k])}
    return f

#单射判断函数
def isinjunction(X,Y,f):
    tv=len(X)==len(getrange(f))
    return tv

#构建满射函数
def surjectionfunc(X,Y):
    m=len(X)
    n=len(Y)
    X0 = random.sample(X,n)
    Y = random.sample(Y,n)
    f=set({})
    for k in range(n):
        f=f|{(X0[k],Y[k])}
        X1=set(X)-set(X0)
        for x in X1:
            y=random.sample(Y,1)[0]
            f=f|{(x,y)}
    return f

#判断满射函数
def issurjection(X,Y,f):
    tv=set(Y)==getrange(f)
    return tv

#构建复合函数
def compositefunc(g,f):
    gf=set({})
    for (x,y) in f:
        for (u,v) in g:
            if(y==u):
                gf.add((x,v))
    return gf

#构建逆函数
def inversefunc(f):
    fv=set({})
    for (x,y) in f:
        fv.add((y,x))
    return fv

#构建指数函数
def powerfunc(fn,f):
    fm=set({})
    for (x,y) in fn:
        for (u,v) in f:
            if(y==u):
                fm.add((x,v))
    return fm

def powernfunc(f,n):
    fn=f
    for k in range(2,n+1):
        fn=powerfunc(fn,f)
    return fn

#阶乘函数，递归参数为n
def Factor(n):
    if(n==1):
        return 1
    return n *Factor(n-1)

#斐波那契函数，递归参数为n
def Fibonacci(n):
    if(n==1 or n==2):
        return 1
    return Fibonacci(n-1)+Fibonacci(n-2)

#阿克曼函数，递归参数为m，n
def Ackemann(m,n):
    if(m==0):
        return(n+1)
    if(n==0):
        return Ackemann(m-1,1)
    return Ackemann(m-1, Ackemann(m,n-1))

#汉诺塔函数，递归参数为n
def Hanoi(n):
    if(n==1):
        return 1
    return 2* Hanoi(n-1)+1